Letter combinations of a phone number

Time: O(Nx4^N); Space: O(N); medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = “23”

Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Explanation:

  • ‘2’ could be ‘a’, ‘b’ or ‘c’

  • ‘3’ could be ‘d’, ‘e’ or ‘f’

Example 2:

Input: digits = “5”

Output: [“j”, “k”, “l”]

Note:

  • Although the above answer is in lexicographical order, your answer could be in any order you want.

[8]:

class Solution1(object):
    """
    Time: O(N*4^N)
    Space: O(N)
    """
    def letterCombinations(self, digits):
        """
        :rtype: List[str]
        """
        if not digits:
            return []

        lookup, result = ['', '', "abc", "def", "ghi", "jkl", "mno",
                          "pqrs", "tuv", "wxyz"], ['']

        for digit in reversed(digits):

            choices = lookup[int(digit)]
            m, n = len(choices), len(result)

            result += [result[i % n] for i in range(n, m * n)]

            for i in range(m * n):
                result[i] = choices[i // n] + result[i]

        return result

[9]:

s = Solution1()
digits = "23"
assert s.letterCombinations(digits) ==  ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
digits = "5"
assert s.letterCombinations(digits) == ["j", "k", "l"]

2. Recursive Solution

[10]:

class Solution2(object):

    def letterCombinations(self, digits):
        """
        :rtype: List[str]
        """
        if not digits:
            return []
        lookup, result = ['', '', "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"], []
        self.letterCombinationsRecu(result, digits, lookup, '', 0)
        return result

    def letterCombinationsRecu(self, result, digits, lookup, cur, n):
        if n == len(digits):
            result.append(cur)
        else:
            for choice in lookup[int(digits[n])]:
                self.letterCombinationsRecu(result, digits, lookup, cur + choice, n + 1)

[11]:

s = Solution2()
digits = "23"
assert s.letterCombinations(digits) ==  ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
digits = "5"
assert s.letterCombinations(digits) == ["j", "k", "l"]